/*-------------------------------------------------------------------------
 *
 * tsrank.c
 *		通过 tsquery 排名 tsvector
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/tsrank.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <limits.h>
#include <math.h>

#include "miscadmin.h"
#include "tsearch/ts_utils.h"
#include "utils/array.h"
#include "utils/builtins.h"

static const float weights[] = {0.1f, 0.2f, 0.4f, 1.0f};

#define wpos(wep)	( fc_w[ WEP_GETWEIGHT(wep) ] )

#define RANK_NO_NORM			0x00
#define RANK_NORM_LOGLENGTH		0x01
#define RANK_NORM_LENGTH		0x02
#define RANK_NORM_EXTDIST		0x04
#define RANK_NORM_UNIQ			0x08
#define RANK_NORM_LOGUNIQ		0x10
#define RANK_NORM_RDIVRPLUS1	0x20
#define DEF_NORM_METHOD			RANK_NO_NORM

static float fc_calc_rank_or(const float *fc_w, TSVector fc_t, TSQuery fc_q);
static float fc_calc_rank_and(const float *fc_w, TSVector fc_t, TSQuery fc_q);

/*
 * 返回单词搭配的权重
 */
static float4 fc_word_distance(int32 fc_w)
{
	if (fc_w > 100)
		return 1e-30f;

	return 1.0 / (1.005 + 0.05 * exp(((float4) fc_w) / 1.5 - 2));
}

static int fc_cnt_length(TSVector fc_t)
{
	WordEntry  *fc_ptr = ARRPTR(fc_t),
			   *fc_end = (WordEntry *) STRPTR(fc_t);
	int			fc_len = 0;

	while (fc_ptr < fc_end)
	{
		int			fc_clen = POSDATALEN(fc_t, fc_ptr);

		if (fc_clen == 0)
			fc_len += 1;
		else
			fc_len += fc_clen;

		fc_ptr++;
	}

	return fc_len;
}


#define WordECompareQueryItem(e,q,p,i,m) \
	tsCompareString((q) + (i)->distance, (i)->length,	\
					(e) + (p)->pos, (p)->len, (m))


/*
 * 返回指向与 tsvector 't' 中 'item' 对应的 WordEntry 数组的指针。
 * 'q' 是包含 'item' 的 TSQuery。
 * 如果未找到，则返回 NULL。
 */
static WordEntry *
fc_find_wordentry(TSVector fc_t, TSQuery fc_q, QueryOperand *fc_item, int32 *fc_nitem)
{
	WordEntry  *fc_StopLow = ARRPTR(fc_t);
	WordEntry  *fc_StopHigh = (WordEntry *) STRPTR(fc_t);
	WordEntry  *fc_StopMiddle = fc_StopHigh;
	int			fc_difference;

	*fc_nitem = 0;

	/* 循环不变式：StopLow <= item < StopHigh */
	while (fc_StopLow < fc_StopHigh)
	{
		fc_StopMiddle = fc_StopLow + (fc_StopHigh - fc_StopLow) / 2;
		fc_difference = WordECompareQueryItem(STRPTR(fc_t), GETOPERAND(fc_q), fc_StopMiddle, fc_item, false);
		if (fc_difference == 0)
		{
			fc_StopHigh = fc_StopMiddle;
			*fc_nitem = 1;
			break;
		}
		else if (fc_difference > 0)
			fc_StopLow = fc_StopMiddle + 1;
		else
			fc_StopHigh = fc_StopMiddle;
	}

	if (fc_item->prefix)
	{
		if (fc_StopLow >= fc_StopHigh)
			fc_StopMiddle = fc_StopHigh;

		*fc_nitem = 0;

		while (fc_StopMiddle < (WordEntry *) STRPTR(fc_t) &&
			   WordECompareQueryItem(STRPTR(fc_t), GETOPERAND(fc_q), fc_StopMiddle, fc_item, true) == 0)
		{
			(*fc_nitem)++;
			fc_StopMiddle++;
		}
	}

	return (*fc_nitem > 0) ? fc_StopHigh : NULL;
}


/*
 * 按 (长度, 单词) 对 QueryOperands 进行排序
 */
static int fc_compareQueryOperand(const void *fc_a, const void *fc_b, void *fc_arg)
{
	char	   *fc_operand = (char *) fc_arg;
	QueryOperand *fc_qa = (*(QueryOperand *const *) fc_a);
	QueryOperand *fc_qb = (*(QueryOperand *const *) fc_b);

	return tsCompareString(fc_operand + fc_qa->distance, fc_qa->length,
						   fc_operand + fc_qb->distance, fc_qb->length,
						   false);
}

/*
 * 返回查询中排序、去重的 QueryOperands 数组。
 * 返回的 QueryOperands 是指向查询中原始 QueryOperands 的指针。
 *
 * 返回数组的长度存储在 *size 中。
 */
static QueryOperand **
fc_SortAndUniqItems(TSQuery fc_q, int *fc_size)
{
	char	   *fc_operand = GETOPERAND(fc_q);
	QueryItem  *fc_item = GETQUERY(fc_q);
	QueryOperand **fc_res,
			  **fc_ptr,
			  **fc_prevptr;

	fc_ptr = fc_res = (QueryOperand **) palloc(sizeof(QueryOperand *) * *fc_size);

	/* 从树中收集所有操作数到 res */
	while ((*fc_size)--)
	{
		if (fc_item->type == QI_VAL)
		{
			*fc_ptr = (QueryOperand *) fc_item;
			fc_ptr++;
		}
		fc_item++;
	}

	*fc_size = fc_ptr - fc_res;
	if (*fc_size < 2)
		return fc_res;

	qsort_arg(fc_res, *fc_size, sizeof(QueryOperand *), fc_compareQueryOperand, (void *) fc_operand);

	fc_ptr = fc_res + 1;
	fc_prevptr = fc_res;

	/* 移除重复项 */
	while (fc_ptr - fc_res < *fc_size)
	{
		if (fc_compareQueryOperand((void *) fc_ptr, (void *) fc_prevptr, (void *) fc_operand) != 0)
		{
			fc_prevptr++;
			*fc_prevptr = *fc_ptr;
		}
		fc_ptr++;
	}

	*fc_size = fc_prevptr + 1 - fc_res;
	return fc_res;
}

static float fc_calc_rank_and(const float *fc_w, TSVector fc_t, TSQuery fc_q)
{
	WordEntryPosVector **fc_pos;
	WordEntryPosVector1 fc_posnull;
	WordEntryPosVector *fc_POSNULL;
	int			fc_i,
				fc_k,
				fc_l,
				fc_p;
	WordEntry  *fc_entry,
			   *fc_firstentry;
	WordEntryPos *fc_post,
			   *fc_ct;
	int32		fc_dimt,
				fc_lenct,
				fc_dist,
				fc_nitem;
	float		fc_res = -1.0;
	QueryOperand **fc_item;
	int			fc_size = fc_q->size;

	fc_item = fc_SortAndUniqItems(fc_q, &fc_size);
	if (fc_size < 2)
	{
		pfree(fc_item);
		return fc_calc_rank_or(fc_w, fc_t, fc_q);
	}
	fc_pos = (WordEntryPosVector **) palloc0(sizeof(WordEntryPosVector *) * fc_q->size);

	/* 当 haspos 为 false 时使用的虚拟 WordEntryPos 数组 */
	fc_posnull.npos = 1;
	fc_posnull.pos[0] = 0;
	WEP_SETPOS(fc_posnull.pos[0], MAXENTRYPOS - 1);
	fc_POSNULL = (WordEntryPosVector *) &fc_posnull;

	for (fc_i = 0; fc_i < fc_size; fc_i++)
	{
		fc_firstentry = fc_entry = fc_find_wordentry(fc_t, fc_q, fc_item[fc_i], &fc_nitem);
		if (!fc_entry)
			continue;

		while (fc_entry - fc_firstentry < fc_nitem)
		{
			if (fc_entry->haspos)
				fc_pos[fc_i] = _POSVECPTR(fc_t, fc_entry);
			else
				fc_pos[fc_i] = fc_POSNULL;

			fc_dimt = fc_pos[fc_i]->npos;
			fc_post = fc_pos[fc_i]->pos;
			for (fc_k = 0; fc_k < fc_i; fc_k++)
			{
				if (!fc_pos[fc_k])
					continue;
				fc_lenct = fc_pos[fc_k]->npos;
				fc_ct = fc_pos[fc_k]->pos;
				for (fc_l = 0; fc_l < fc_dimt; fc_l++)
				{
					for (fc_p = 0; fc_p < fc_lenct; fc_p++)
					{
						fc_dist = Abs((int) WEP_GETPOS(fc_post[fc_l]) - (int) WEP_GETPOS(fc_ct[fc_p]));
						if (fc_dist || (fc_dist == 0 && (fc_pos[fc_i] == fc_POSNULL || fc_pos[fc_k] == fc_POSNULL)))
						{
							float		fc_curw;

							if (!fc_dist)
								fc_dist = MAXENTRYPOS;
							fc_curw = sqrt(wpos(fc_post[fc_l]) * wpos(fc_ct[fc_p]) * fc_word_distance(fc_dist));
							fc_res = (fc_res < 0) ? fc_curw : 1.0 - (1.0 - fc_res) * (1.0 - fc_curw);
						}
					}
				}
			}

			fc_entry++;
		}
	}
	pfree(fc_pos);
	pfree(fc_item);
	return fc_res;
}

static float fc_calc_rank_or(const float *fc_w, TSVector fc_t, TSQuery fc_q)
{
	WordEntry  *fc_entry,
			   *fc_firstentry;
	WordEntryPosVector1 fc_posnull;
	WordEntryPos *fc_post;
	int32		fc_dimt,
				fc_j,
				fc_i,
				fc_nitem;
	float		fc_res = 0.0;
	QueryOperand **fc_item;
	int			fc_size = fc_q->size;

	/* 当 haspos 为 false 时使用的虚拟 WordEntryPos 数组 */
	fc_posnull.npos = 1;
	fc_posnull.pos[0] = 0;

	fc_item = fc_SortAndUniqItems(fc_q, &fc_size);

	for (fc_i = 0; fc_i < fc_size; fc_i++)
	{
		float		fc_resj,
					fc_wjm;
		int32		fc_jm;

		fc_firstentry = fc_entry = fc_find_wordentry(fc_t, fc_q, fc_item[fc_i], &fc_nitem);
		if (!fc_entry)
			continue;

		while (fc_entry - fc_firstentry < fc_nitem)
		{
			if (fc_entry->haspos)
			{
				fc_dimt = POSDATALEN(fc_t, fc_entry);
				fc_post = POSDATAPTR(fc_t, fc_entry);
			}
			else
			{
				fc_dimt = fc_posnull.npos;
				fc_post = fc_posnull.pos;
			}

			fc_resj = 0.0;
			fc_wjm = -1.0;
			fc_jm = 0;
			for (fc_j = 0; fc_j < fc_dimt; fc_j++)
			{
				fc_resj = fc_resj + wpos(fc_post[fc_j]) / ((fc_j + 1) * (fc_j + 1));
				if (wpos(fc_post[fc_j]) > fc_wjm)
				{
					fc_wjm = wpos(fc_post[fc_j]);
					fc_jm = fc_j;
				}
			}
/*
			limit (sum(1/i^2),i=1,inf) = pi^2/6
			resj = sum(wi/i^2),i=1,noccurrence,
			wi - 应该按降序排序，
			暂时不要排序，只选择最大权重。这应该被修正
			Oleg Bartunov
*/
			fc_res = fc_res + (fc_wjm + fc_resj - fc_wjm / ((fc_jm + 1) * (fc_jm + 1))) / 1.64493406685;

			fc_entry++;
		}
	}
	if (fc_size > 0)
		fc_res = fc_res / fc_size;
	pfree(fc_item);
	return fc_res;
}

static float fc_calc_rank(const float *fc_w, TSVector fc_t, TSQuery fc_q, int32 fc_method)
{
	QueryItem  *fc_item = GETQUERY(fc_q);
	float		fc_res = 0.0;
	int			fc_len;

	if (!fc_t->size || !fc_q->size)
		return 0.0;

	/* XXX: NOT 怎么办？ */
	fc_res = (fc_item->type == QI_OPR && (fc_item->qoperator.oper == OP_AND ||
									fc_item->qoperator.oper == OP_PHRASE)) ?
		fc_calc_rank_and(fc_w, fc_t, fc_q) :
		fc_calc_rank_or(fc_w, fc_t, fc_q);

	if (fc_res < 0)
		fc_res = 1e-20f;

	if ((fc_method & RANK_NORM_LOGLENGTH) && fc_t->size > 0)
		fc_res /= log((double) (fc_cnt_length(fc_t) + 1)) / log(2.0);

	if (fc_method & RANK_NORM_LENGTH)
	{
		fc_len = fc_cnt_length(fc_t);
		if (fc_len > 0)
			fc_res /= (float) fc_len;
	}

	/* RANK_NORM_EXTDIST 不适用 */

	if ((fc_method & RANK_NORM_UNIQ) && fc_t->size > 0)
		fc_res /= (float) (fc_t->size);

	if ((fc_method & RANK_NORM_LOGUNIQ) && fc_t->size > 0)
		fc_res /= log((double) (fc_t->size + 1)) / log(2.0);

	if (fc_method & RANK_NORM_RDIVRPLUS1)
		fc_res /= (fc_res + 1);

	return fc_res;
}

static const float *
fc_getWeights(ArrayType *fc_win)
{
	static float fc_ws[lengthof(weights)];
	int			fc_i;
	float4	   *fc_arrdata;

	if (fc_win == NULL)
		return weights;

	if (ARR_NDIM(fc_win) != 1)
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
				 errmsg("array of weight must be one-dimensional")));

	if (ArrayGetNItems(ARR_NDIM(fc_win), ARR_DIMS(fc_win)) < lengthof(weights))
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
				 errmsg("array of weight is too short")));

	if (array_contains_nulls(fc_win))
		ereport(ERROR,
				(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
				 errmsg("array of weight must not contain nulls")));

	fc_arrdata = (float4 *) ARR_DATA_PTR(fc_win);
	for (fc_i = 0; fc_i < lengthof(weights); fc_i++)
	{
		fc_ws[fc_i] = (fc_arrdata[fc_i] >= 0) ? fc_arrdata[fc_i] : weights[fc_i];
		if (fc_ws[fc_i] > 1.0)
			ereport(ERROR,
					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
					 errmsg("weight out of range")));
	}

	return fc_ws;
}

Datum ts_rank_wttf(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
	TSVector	fc_txt = PG_GETARG_TSVECTOR(1);
	TSQuery		fc_query = PG_GETARG_TSQUERY(2);
	int			fc_method = PG_GETARG_INT32(3);
	float		fc_res;

	fc_res = fc_calc_rank(fc_getWeights(fc_win), fc_txt, fc_query, fc_method);

	PG_FREE_IF_COPY(fc_win, 0);
	PG_FREE_IF_COPY(fc_txt, 1);
	PG_FREE_IF_COPY(fc_query, 2);
	PG_RETURN_FLOAT4(fc_res);
}

Datum ts_rank_wtt(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
	TSVector	fc_txt = PG_GETARG_TSVECTOR(1);
	TSQuery		fc_query = PG_GETARG_TSQUERY(2);
	float		fc_res;

	fc_res = fc_calc_rank(fc_getWeights(fc_win), fc_txt, fc_query, DEF_NORM_METHOD);

	PG_FREE_IF_COPY(fc_win, 0);
	PG_FREE_IF_COPY(fc_txt, 1);
	PG_FREE_IF_COPY(fc_query, 2);
	PG_RETURN_FLOAT4(fc_res);
}

Datum ts_rank_ttf(PG_FUNCTION_ARGS)
{
	TSVector	fc_txt = PG_GETARG_TSVECTOR(0);
	TSQuery		fc_query = PG_GETARG_TSQUERY(1);
	int			fc_method = PG_GETARG_INT32(2);
	float		fc_res;

	fc_res = fc_calc_rank(fc_getWeights(NULL), fc_txt, fc_query, fc_method);

	PG_FREE_IF_COPY(fc_txt, 0);
	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_FLOAT4(fc_res);
}

Datum ts_rank_tt(PG_FUNCTION_ARGS)
{
	TSVector	fc_txt = PG_GETARG_TSVECTOR(0);
	TSQuery		fc_query = PG_GETARG_TSQUERY(1);
	float		fc_res;

	fc_res = fc_calc_rank(fc_getWeights(NULL), fc_txt, fc_query, DEF_NORM_METHOD);

	PG_FREE_IF_COPY(fc_txt, 0);
	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_FLOAT4(fc_res);
}

typedef struct
{
	union
	{
		struct
		{						/* 编译的文档表示 */
			QueryItem **items;
			int16		nitem;
		}			query;
		struct
		{						/* 结构用于准备文档
								 * 表示 */
			QueryItem  *item;
			WordEntry  *entry;
		}			map;
	}			data;
	WordEntryPos pos;
} DocRepresentation;

static int fc_compareDocR(const void *fc_va, const void *fc_vb)
{
	const DocRepresentation *fc_a = (const DocRepresentation *) fc_va;
	const DocRepresentation *fc_b = (const DocRepresentation *) fc_vb;

	if (WEP_GETPOS(fc_a->pos) == WEP_GETPOS(fc_b->pos))
	{
		if (WEP_GETWEIGHT(fc_a->pos) == WEP_GETWEIGHT(fc_b->pos))
		{
			if (fc_a->data.map.entry == fc_b->data.map.entry)
				return 0;

			return (fc_a->data.map.entry > fc_b->data.map.entry) ? 1 : -1;
		}

		return (WEP_GETWEIGHT(fc_a->pos) > WEP_GETWEIGHT(fc_b->pos)) ? 1 : -1;
	}

	return (WEP_GETPOS(fc_a->pos) > WEP_GETPOS(fc_b->pos)) ? 1 : -1;
}

#define MAXQROPOS	MAXENTRYPOS
typedef struct
{
	bool		operandexists;
	bool		reverseinsert;	/* 表示插入顺序，true 意味着
								 * 降序 */
	uint32		npos;
	WordEntryPos pos[MAXQROPOS];
} QueryRepresentationOperand;

typedef struct
{
	TSQuery		query;
	QueryRepresentationOperand *operandData;
} QueryRepresentation;

#define QR_GET_OPERAND_DATA(q, v) \
	( (q)->operandData + (((QueryItem*)(v)) - GETQUERY((q)->query)) )

/*
 * TS_execute 回调，用于匹配 tsquery 操作数与 QueryRepresentation
 */
static TSTernaryValue fc_checkcondition_QueryOperand(void *fc_checkval, QueryOperand *fc_val,
							ExecPhraseData *fc_data)
{
	QueryRepresentation *fc_qr = (QueryRepresentation *) fc_checkval;
	QueryRepresentationOperand *fc_opData = QR_GET_OPERAND_DATA(fc_qr, fc_val);

	if (!fc_opData->operandexists)
		return TS_NO;

	if (fc_data)
	{
		fc_data->npos = fc_opData->npos;
		fc_data->pos = fc_opData->pos;
		if (fc_opData->reverseinsert)
			fc_data->pos += MAXQROPOS - fc_opData->npos;
	}

	return TS_YES;
}

typedef struct
{
	int			pos;
	int			p;
	int			q;
	DocRepresentation *begin;
	DocRepresentation *end;
} CoverExt;

static void fc_resetQueryRepresentation(QueryRepresentation *fc_qr, bool fc_reverseinsert)
{
	int			fc_i;

	for (fc_i = 0; fc_i < fc_qr->query->size; fc_i++)
	{
		fc_qr->operandData[fc_i].operandexists = false;
		fc_qr->operandData[fc_i].reverseinsert = fc_reverseinsert;
		fc_qr->operandData[fc_i].npos = 0;
	}
}

static void fc_fillQueryRepresentationData(QueryRepresentation *fc_qr, DocRepresentation *fc_entry)
{
	int			fc_i;
	int			fc_lastPos;
	QueryRepresentationOperand *fc_opData;

	for (fc_i = 0; fc_i < fc_entry->data.query.nitem; fc_i++)
	{
		if (fc_entry->data.query.items[fc_i]->type != QI_VAL)
			continue;

		fc_opData = QR_GET_OPERAND_DATA(fc_qr, fc_entry->data.query.items[fc_i]);

		fc_opData->operandexists = true;

		if (fc_opData->npos == 0)
		{
			fc_lastPos = (fc_opData->reverseinsert) ? (MAXQROPOS - 1) : 0;
			fc_opData->pos[fc_lastPos] = fc_entry->pos;
			fc_opData->npos++;
			continue;
		}

		fc_lastPos = fc_opData->reverseinsert ?
			(MAXQROPOS - fc_opData->npos) :
			(fc_opData->npos - 1);

		if (WEP_GETPOS(fc_opData->pos[fc_lastPos]) != WEP_GETPOS(fc_entry->pos))
		{
			fc_lastPos = fc_opData->reverseinsert ?
				(MAXQROPOS - 1 - fc_opData->npos) :
				(fc_opData->npos);

			fc_opData->pos[fc_lastPos] = fc_entry->pos;
			fc_opData->npos++;
		}
	}
}

static bool fc_Cover(DocRepresentation *fc_doc, int fc_len, QueryRepresentation *fc_qr, CoverExt *fc_ext)
{
	DocRepresentation *fc_ptr;
	int			fc_lastpos = fc_ext->pos;
	bool		fc_found = false;

	/*
	 * 由于此函数递归，可能会导致堆栈溢出。
	 * （尽管任何优秀的编译器会优化掉尾递归。）
	 */
	check_stack_depth();

	fc_resetQueryRepresentation(fc_qr, false);

	fc_ext->p = INT_MAX;
	fc_ext->q = 0;
	fc_ptr = fc_doc + fc_ext->pos;

	/* 从当前位置查找封闭的上界，向上移动 */
	while (fc_ptr - fc_doc < fc_len)
	{
		fc_fillQueryRepresentationData(fc_qr, fc_ptr);

		if (TS_execute(GETQUERY(fc_qr->query), (void *) fc_qr,
					   TS_EXEC_EMPTY, fc_checkcondition_QueryOperand))
		{
			if (WEP_GETPOS(fc_ptr->pos) > fc_ext->q)
			{
				fc_ext->q = WEP_GETPOS(fc_ptr->pos);
				fc_ext->end = fc_ptr;
				fc_lastpos = fc_ptr - fc_doc;
				fc_found = true;
			}
			break;
		}
		fc_ptr++;
	}

	if (!fc_found)
		return false;

	fc_resetQueryRepresentation(fc_qr, true);

	fc_ptr = fc_doc + fc_lastpos;

	/* 从找到的上界查找封闭的下界，向下移动 */
	while (fc_ptr >= fc_doc + fc_ext->pos)
	{
		/*
		 * 我们从右到左扫描文档，所以位置信息是反向的！
		 */
		fc_fillQueryRepresentationData(fc_qr, fc_ptr);

		if (TS_execute(GETQUERY(fc_qr->query), (void *) fc_qr,
					   TS_EXEC_EMPTY, fc_checkcondition_QueryOperand))
		{
			if (WEP_GETPOS(fc_ptr->pos) < fc_ext->p)
			{
				fc_ext->begin = fc_ptr;
				fc_ext->p = WEP_GETPOS(fc_ptr->pos);
			}
			break;
		}
		fc_ptr--;
	}

	if (fc_ext->p <= fc_ext->q)
	{
		/*
		 * 设置下一次尝试的位置为找到的
		 * 封闭的开始之后的下一个词素
		 */
		fc_ext->pos = (fc_ptr - fc_doc) + 1;
		return true;
	}

	fc_ext->pos++;
	return fc_Cover(fc_doc, fc_len, fc_qr, fc_ext);
}

static DocRepresentation *
get_docrep(TSVector fc_txt, QueryRepresentation *fc_qr, int *fc_doclen)
{
	QueryItem  *fc_item = GETQUERY(fc_qr->query);
	WordEntry  *fc_entry,
			   *fc_firstentry;
	WordEntryPos *fc_post;
	int32		fc_dimt,			/* 'post' 项目的数量 */
				fc_j,
				fc_i,
				fc_nitem;
	int			fc_len = fc_qr->query->size * 4,
				fc_cur = 0;
	DocRepresentation *fc_doc;

	fc_doc = (DocRepresentation *) palloc(sizeof(DocRepresentation) * fc_len);

	/*
	 * 遍历查询为满足查询的单词及其
	 * 条目制作 DocRepresentation
	 */
	for (fc_i = 0; fc_i < fc_qr->query->size; fc_i++)
	{
		QueryOperand *fc_curoperand;

		if (fc_item[fc_i].type != QI_VAL)
			continue;

		fc_curoperand = &fc_item[fc_i].qoperand;

		fc_firstentry = fc_entry = fc_find_wordentry(fc_txt, fc_qr->query, fc_curoperand, &fc_nitem);
		if (!fc_entry)
			continue;

		/* 在 tsvector 中对条目进行迭代 */
		while (fc_entry - fc_firstentry < fc_nitem)
		{
			if (fc_entry->haspos)
			{
				fc_dimt = POSDATALEN(fc_txt, fc_entry);
				fc_post = POSDATAPTR(fc_txt, fc_entry);
			}
			else
			{
				/* 忽略没有位置的词 */
				fc_entry++;
				continue;
			}

			while (fc_cur + fc_dimt >= fc_len)
			{
				fc_len *= 2;
				fc_doc = (DocRepresentation *) repalloc(fc_doc, sizeof(DocRepresentation) * fc_len);
			}

			/* 对条目的位置进行迭代 */
			for (fc_j = 0; fc_j < fc_dimt; fc_j++)
			{
				if (fc_curoperand->weight == 0 ||
					fc_curoperand->weight & (1 << WEP_GETWEIGHT(fc_post[fc_j])))
				{
					fc_doc[fc_cur].pos = fc_post[fc_j];
					fc_doc[fc_cur].data.map.entry = fc_entry;
					fc_doc[fc_cur].data.map.item = (QueryItem *) fc_curoperand;
					fc_cur++;
				}
			}

			fc_entry++;
		}
	}

	if (fc_cur > 0)
	{
		DocRepresentation *fc_rptr = fc_doc + 1,
				   *fc_wptr = fc_doc,
					fc_storage;

		/*
		 * 按 pos 和条目升序排序表示
		 */
		qsort((void *) fc_doc, fc_cur, sizeof(DocRepresentation), fc_compareDocR);

		/*
		 * 根据 WordEntry 和它的位置连接 QueryItem
		 */
		fc_storage.pos = fc_doc->pos;
		fc_storage.data.query.items = palloc(sizeof(QueryItem *) * fc_qr->query->size);
		fc_storage.data.query.items[0] = fc_doc->data.map.item;
		fc_storage.data.query.nitem = 1;

		while (fc_rptr - fc_doc < fc_cur)
		{
			if (fc_rptr->pos == (fc_rptr - 1)->pos &&
				fc_rptr->data.map.entry == (fc_rptr - 1)->data.map.entry)
			{
				fc_storage.data.query.items[fc_storage.data.query.nitem] = fc_rptr->data.map.item;
				fc_storage.data.query.nitem++;
			}
			else
			{
				*fc_wptr = fc_storage;
				fc_wptr++;
				fc_storage.pos = fc_rptr->pos;
				fc_storage.data.query.items = palloc(sizeof(QueryItem *) * fc_qr->query->size);
				fc_storage.data.query.items[0] = fc_rptr->data.map.item;
				fc_storage.data.query.nitem = 1;
			}

			fc_rptr++;
		}

		*fc_wptr = fc_storage;
		fc_wptr++;

		*fc_doclen = fc_wptr - fc_doc;
		return fc_doc;
	}

	pfree(fc_doc);
	return NULL;
}

static float4 fc_calc_rank_cd(const float4 *fc_arrdata, TSVector fc_txt, TSQuery fc_query, int fc_method)
{
	DocRepresentation *fc_doc;
	int			fc_len,
				fc_i,
				fc_doclen = 0;
	CoverExt	fc_ext;
	double		fc_Wdoc = 0.0;
	double		fc_invws[lengthof(weights)];
	double		fc_SumDist = 0.0,
				fc_PrevExtPos = 0.0;
	int			fc_NExtent = 0;
	QueryRepresentation fc_qr;


	for (fc_i = 0; fc_i < lengthof(weights); fc_i++)
	{
		fc_invws[fc_i] = ((double) ((fc_arrdata[fc_i] >= 0) ? fc_arrdata[fc_i] : weights[fc_i]));
		if (fc_invws[fc_i] > 1.0)
			ereport(ERROR,
					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
					 errmsg("weight out of range")));
		fc_invws[fc_i] = 1.0 / fc_invws[fc_i];
	}

	fc_qr.query = fc_query;
	fc_qr.operandData = (QueryRepresentationOperand *)
		palloc0(sizeof(QueryRepresentationOperand) * fc_query->size);

	fc_doc = get_docrep(fc_txt, &fc_qr, &fc_doclen);
	if (!fc_doc)
	{
		pfree(fc_qr.operandData);
		return 0.0;
	}

	MemSet(&fc_ext, 0, sizeof(CoverExt));
	while (fc_Cover(fc_doc, fc_doclen, &fc_qr, &fc_ext))
	{
		double		fc_Cpos = 0.0;
		double		fc_InvSum = 0.0;
		double		fc_CurExtPos;
		int			fc_nNoise;
		DocRepresentation *fc_ptr = fc_ext.begin;

		while (fc_ptr <= fc_ext.end)
		{
			fc_InvSum += fc_invws[WEP_GETWEIGHT(fc_ptr->pos)];
			fc_ptr++;
		}

		fc_Cpos = ((double) (fc_ext.end - fc_ext.begin + 1)) / fc_InvSum;

		/*
		 * 如果文档足够大，则 ext.q 可能等于 ext.p，因位置
		 * 信息的限制。在这种情况下，我们将噪声词的数量近似为封面的长度的一半
		 */
		fc_nNoise = (fc_ext.q - fc_ext.p) - (fc_ext.end - fc_ext.begin);
		if (fc_nNoise < 0)
			fc_nNoise = (fc_ext.end - fc_ext.begin) / 2;
		fc_Wdoc += fc_Cpos / ((double) (1 + fc_nNoise));

		fc_CurExtPos = ((double) (fc_ext.q + fc_ext.p)) / 2.0;
		if (fc_NExtent > 0 && fc_CurExtPos > fc_PrevExtPos	/* 防止在多个 lexize 的情况下出现
													 * 除以零的情况 */ )
			fc_SumDist += 1.0 / (fc_CurExtPos - fc_PrevExtPos);

		fc_PrevExtPos = fc_CurExtPos;
		fc_NExtent++;
	}

	if ((fc_method & RANK_NORM_LOGLENGTH) && fc_txt->size > 0)
		fc_Wdoc /= log((double) (fc_cnt_length(fc_txt) + 1));

	if (fc_method & RANK_NORM_LENGTH)
	{
		fc_len = fc_cnt_length(fc_txt);
		if (fc_len > 0)
			fc_Wdoc /= (double) fc_len;
	}

	if ((fc_method & RANK_NORM_EXTDIST) && fc_NExtent > 0 && fc_SumDist > 0)
		fc_Wdoc /= ((double) fc_NExtent) / fc_SumDist;

	if ((fc_method & RANK_NORM_UNIQ) && fc_txt->size > 0)
		fc_Wdoc /= (double) (fc_txt->size);

	if ((fc_method & RANK_NORM_LOGUNIQ) && fc_txt->size > 0)
		fc_Wdoc /= log((double) (fc_txt->size + 1)) / log(2.0);

	if (fc_method & RANK_NORM_RDIVRPLUS1)
		fc_Wdoc /= (fc_Wdoc + 1);

	pfree(fc_doc);

	pfree(fc_qr.operandData);

	return (float4) fc_Wdoc;
}

Datum ts_rankcd_wttf(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
	TSVector	fc_txt = PG_GETARG_TSVECTOR(1);
	TSQuery		fc_query = PG_GETARG_TSQUERY(2);
	int			fc_method = PG_GETARG_INT32(3);
	float		fc_res;

	fc_res = fc_calc_rank_cd(fc_getWeights(fc_win), fc_txt, fc_query, fc_method);

	PG_FREE_IF_COPY(fc_win, 0);
	PG_FREE_IF_COPY(fc_txt, 1);
	PG_FREE_IF_COPY(fc_query, 2);
	PG_RETURN_FLOAT4(fc_res);
}

Datum ts_rankcd_wtt(PG_FUNCTION_ARGS)
{
	ArrayType  *fc_win = (ArrayType *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
	TSVector	fc_txt = PG_GETARG_TSVECTOR(1);
	TSQuery		fc_query = PG_GETARG_TSQUERY(2);
	float		fc_res;

	fc_res = fc_calc_rank_cd(fc_getWeights(fc_win), fc_txt, fc_query, DEF_NORM_METHOD);

	PG_FREE_IF_COPY(fc_win, 0);
	PG_FREE_IF_COPY(fc_txt, 1);
	PG_FREE_IF_COPY(fc_query, 2);
	PG_RETURN_FLOAT4(fc_res);
}

Datum ts_rankcd_ttf(PG_FUNCTION_ARGS)
{
	TSVector	fc_txt = PG_GETARG_TSVECTOR(0);
	TSQuery		fc_query = PG_GETARG_TSQUERY(1);
	int			fc_method = PG_GETARG_INT32(2);
	float		fc_res;

	fc_res = fc_calc_rank_cd(fc_getWeights(NULL), fc_txt, fc_query, fc_method);

	PG_FREE_IF_COPY(fc_txt, 0);
	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_FLOAT4(fc_res);
}

Datum ts_rankcd_tt(PG_FUNCTION_ARGS)
{
	TSVector	fc_txt = PG_GETARG_TSVECTOR(0);
	TSQuery		fc_query = PG_GETARG_TSQUERY(1);
	float		fc_res;

	fc_res = fc_calc_rank_cd(fc_getWeights(NULL), fc_txt, fc_query, DEF_NORM_METHOD);

	PG_FREE_IF_COPY(fc_txt, 0);
	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_FLOAT4(fc_res);
}
